// url: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-interview-150
package interview_classic.array_or_str;

import java.util.ArrayList;
import java.util.List;

public class Solution121 {

    // 采用动态规划
    public int maxProfit(int[] prices) {
        int cost = Integer.MAX_VALUE, profit = 0;
        for (Integer price: prices) {
            cost = Math.min(cost, price); // 计算历史最小的价格
            profit = Math.max(price - cost, profit); // 当前价格与历史最小价格得出当前最大的利润 在于历史最大利润比较
        }
        return profit;
    }

    // bad time over!!!
    public static int maxProfit2(int[] prices) {
        int len = prices.length;
        if (len == 1 || len == 0) return 0;
        List<Integer> minIndex = new ArrayList<>(), maxIndex = new ArrayList<>();
        if (prices[0] < prices[1]) {
            minIndex.add(0);
        }

        for (int i = 1; i < len - 1; i++) {
            if (prices[i - 1] >= prices[i] && prices[i] < prices[i + 1]) {
                minIndex.add(i);
            }
            if (prices[i - 1] <= prices[i] && prices[i] > prices[i + 1]) {
                maxIndex.add(i);
            }
        }
        if (prices[len - 2] < prices[len - 1]) {
            maxIndex.add(len - 1);
        }
        int ret = 0, minLen = minIndex.size(), maxLen = maxIndex.size();
        for (int i = 0; i < minLen; i++) {
            for (int j = 0; j < maxLen; j++) {
                int minI = minIndex.get(i), maxI = maxIndex.get(maxLen - 1 - j);
                if (minI > maxI) break;
                if (prices[maxI] - prices[minI] < 0) continue;
                if (prices[maxI] - prices[minI] > ret) ret = prices[maxI] - prices[minI];
            }
        }
        return ret;
    }

}
